package com.south.base.test.arithmetic.arrays;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Administrator
 * @date 2020/7/21 9:32
 */
public class Cartesian {
    /**
     * 笛卡尔积
     */
    @Test
    public void cartesian() {
        cartesian(new int[][]{{1, 2}, {3, 4, 5}, {6, 7}});
        cartesian(new int[][]{{1, 2}, {3, 4, 5}, {6, 7}, {8, 9, 10}, {11, 12, 13, 14}});
        cartesian2(new int[][]{{1, 2}, {3, 4, 5}, {6, 7}});
        cartesian2(new int[][]{{1, 2}, {3, 4, 5}, {6, 7}, {8, 9, 10}, {11, 12, 13, 14}});
        cartesian3(new int[][]{{1, 2}, {3, 4, 5}, {6, 7}});
        cartesian3(new int[][]{{1, 2}, {3, 4, 5}, {6, 7}, {8, 9, 10}, {11, 12, 13, 14}});
    }

    /**
     * 不构建、直接模拟字典树遍历
     * @param inputs
     */
    public void cartesian3(int[][] inputs) {
        cartesian3(inputs, 0, new StringBuilder());
    }

    public void cartesian3(int[][] inputs, int x, StringBuilder stringBuilder) {
        if (x == inputs.length) {
            stringBuilder.delete(stringBuilder.length() - 1, stringBuilder.length());
            System.out.println(stringBuilder.toString());
            return;
        }
        for (int i = 0; i < inputs[x].length; i++) {
            stringBuilder.append(inputs[x][i]).append(",");
            cartesian3(inputs, x + 1, stringBuilder);
            int index = stringBuilder.lastIndexOf(",") + 1;
            stringBuilder.delete(index < 0 ? stringBuilder.length() : index, stringBuilder.length());
        }
        int index = stringBuilder.lastIndexOf(",");
        if (index > 0) {
            stringBuilder.deleteCharAt(index);
        }
    }

    /**
     * 字典树
     *
     * @param inputs
     */
    public void cartesian2(int[][] inputs) {
        List<Node> tmp = new ArrayList<>();
        List<Node> tmp2 = new ArrayList<>();
        for (int i = inputs.length - 1; i >= 0; i--) {
            for (int j = 0; j < inputs[i].length; j++) {
                Node node = new Node();
                node.val = inputs[i][j];
                tmp.add(node);
                node.nodes = tmp2;
            }
            tmp2 = tmp;
            tmp = new ArrayList<>();
        }
        cartesian2(tmp2, new StringBuilder());
    }

    public void cartesian2(List<Node> nodes, StringBuilder stringBuilder) {
        if (nodes == null || nodes.size() == 0) {
            stringBuilder.delete(stringBuilder.length() - 1, stringBuilder.length());
            System.out.println(stringBuilder.toString());
            return;
        }
        for (int i = 0; i < nodes.size(); i++) {
            stringBuilder.append(nodes.get(i).val).append(",");
            cartesian2(nodes.get(i).nodes, stringBuilder);
            int index = stringBuilder.lastIndexOf(",") + 1;
            stringBuilder.delete(index < 0 ? stringBuilder.length() : index, stringBuilder.length());
        }
        int index = stringBuilder.lastIndexOf(",");
        if (index > 0) {
            stringBuilder.deleteCharAt(index);
        }
    }

    /**
     * 保利解法
     *
     * @param inputs
     */
    public void cartesian(int[][] inputs) {
        if (inputs == null || inputs.length == 0) {
            return;
        }
        List<String> strings = new ArrayList<>();
        for (int i = 0; i < inputs[0].length; i++) {
            strings.add(String.valueOf(inputs[0][i]));
        }
        for (int i = 1; i < inputs.length; i++) {
            List<String> tmp = new ArrayList<>();
            for (int j = 0; j < inputs[i].length; j++) {
                for (String string : strings) {
                    tmp.add(string + "," + inputs[i][j]);
                }
            }
            strings = tmp;
        }
        for (String string : strings) {
            System.out.println(string);
        }
    }

    class Node {
        List<Node> nodes;
        int val;
    }
}
